#include <string>
#include "SuffixArray.h"
using namespace std;


int SuffixArray::sufCompare(const char* a, const char* b, int lenWord, int lenSuf) {
	int same = 0;
    while (same < lenWord && same <lenSuf) {
		if (tolower(*a) == tolower(*b)) {
			same++;
		}
        else {
			break;
		}
        a++;
        b++;
    }

    if (same == lenWord) { return 0; };
	if (same==lenSuf) {
		return 1;
	}
    if (tolower(*a) > tolower(*b)) {
		return 1;
	}
    return -1;
}
void SuffixArray::binSearch(const string& value, vector<int>& indexes, int l, int r) {
	if (l>r || l<0 || r>=s.size()-1) {
		return;
	}
	int middle=(l+r)/2;
	int lenWord=value.length();
	int cmp=sufCompare(&value[0], &s[p[middle]], value.length(), s.length()-p[middle]-1); // результат сравнения
	if (cmp==0) {
		indexes.push_back(p[middle]);
		//cout<<p[middle]<<endl;
		int toend=middle+1;
		int tobegin=middle-1;
		while (toend<p.size()) {
			if (sufCompare(&value[0], &s[p[toend]], value.length(), s.length()-p[toend]-1)!=0) {
				break;
			}
			indexes.push_back(p[toend]);
			toend++;
		}

		while (tobegin>-1) {
			if (sufCompare(&value[0], &s[p[tobegin]], value.length(), s.length()-p[tobegin]-1)!=0) {
				break;
			}
			indexes.push_back(p[tobegin]);
			tobegin--;
		}

	} else if (cmp==-1) {
		binSearch(value, indexes, l, middle-1);
	} else {
		binSearch(value, indexes, middle+1, r);
	}
 
}


void SuffixArray::Build(const string & ss)
	{
		//Инициализация
		s = ss + '\0';
		n = s.size();
 
		c.resize(n);
		p.resize(n);
		cn.resize(n);
		pn.resize(n);
 
		// Нулевая фаза алгоритма
		cnt.assign(ALPHABET, 0);
 
		// Инициализация перестановки
		for(int i = 0; i < n; i++)
		{
			cnt[tolower(s[i])]++;
		}
		for(int i = 1; i < ALPHABET; i++)
		{
			cnt[i] += cnt[i-1];
		}
		for(int i = n-1; i >= 0; i--)
		{
			p[--cnt[tolower(s[i])]] = i;
		}
 
		//Инициализация классов
		int csize = 0; // количество классов
		c[p[0]] = csize;
		for(int i = 1; i < n; i++)
		{
			if (s[p[i]] != s[p[i-1]])
			{
				csize ++;
			}
			c[p[i]] = csize;
		}
		csize++;
 
		for(int l = 1; l < n; l *= 2)
		{
			// log(l) фаза алгоритма
 
			//Изменение перестановки
			cnt.assign(csize, 0);
			for(int i = 0; i < n; i++)
			{
				pn[i] = (p[i] - l + n)%n;
			}
			for(int i = 0; i < n; i++)
			{
				cnt[c[pn[i]]]++;
			}
			for(int i = 1; i < csize; i++)
			{
				cnt[i] += cnt[i-1];
			}
			for(int i = n-1; i >= 0; i--)
			{
				p[--cnt[c[pn[i]]]] = pn[i]; 
			}
 
			//Изменение классов
			csize = 0;
			cn[p[0]] = csize;
			for(int i = 1; i < n; i++)
			{
				if(c[p[i]] != c[p[i-1]] || c[(p[i]+l)%n] != c[(p[i-1]+l)%n])
				{
					csize++;
				}
				cn[p[i]] = csize;
			}
			csize++;
			c = cn;
		}


		/*for (int i=0; i<ss.size(); i++)  {
			cout<<ss.substr(p[i], ss.length()-1)<<endl;
		}*/
	}
